We introduce collapsed compilation, a novel approximate inference algorithm for discrete probabilistic graphical models. It is a collapsed sampling algorithm that incrementally selects which variable to sample next based on the partial compilation obtained so far. This online collapsing, together with knowledge compilation inference on the remaining variables, naturally exploits local structure and context-specific independence in the distribution. These properties are used implicitly in exact inference, but are difficult to harness for approximate inference. Moreover, by having a partially compiled circuit available during sampling, collapsed compilation has access to a highly effective proposal distribution for importance sampling. Our experimental evaluation shows that collapsed compilation performs well on standard benchmarks. In particular, when the amount of exact inference is equally limited, collapsed compilation is competitive with the state of the art, and outperforms it on several benchmarks.

The paper proposes an approach for approximate inference in discrete graphical models that generalizes collapsed importance sampling. The apprach is online, in the sense that the choice of variables to sample depends on the values already sampled, instead of being fixed. Moreover, the exact inference portion of the method is performed by knwoledge compilation so the approach is called collapsed compilation and allows approximate knowledge compilation. The method begins by multiplying factors obtaining a Sentential Decision Diagram. When the SDD becomes too large, a variable is deterministically chosen, a value for it is sampled from a proposal distribution that is the marginal of the variable in the current SDD and the SDD is conditioned on the sampled value.

We introduce collapsed compilation, a novel approximate inference algorithm for discrete probabilistic graphical models. It is a collapsed sampling algorithm that incrementally selects which variable to sample next based on the partial compila- tion obtained so far. This online collapsing, together with knowledge compilation inference on the remaining variables, naturally exploits local structure and context- specific independence in the distribution. These properties are used implicitly in exact inference, but are difficult to harness for approximate inference. More- over, by having a partially compiled circuit available during sampling, collapsed compilation has access to a highly effective proposal distribution for importance sampling.